package node;

import javax.print.DocFlavor;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        String str = "abc abd abc abc abc abc abd abd";
        String str1 = "a a b a b b ca ca ca a b a b";
        for (String s : StringMostStr(str,3)){
            System.out.println(s);
        }



        for (String s : StringMostStr(str1,5)){
            System.out.println(s);
        }
    }

    public static ArrayList<String> StringMostStr(String str,int n){
        ArrayList<String> arrList = new ArrayList<>();
        if (str =="" || n<=0){
            return  arrList;
        }
        String[] arr = str.split(" ");
        HashMap<String,Integer>  map= new HashMap<>();
        for (String a:arr){
            if (!map.containsKey(a)){
                map.put(a,1);
            }else {
                map.put(a,map.get(a)+1);
            }
        }
        Set<String> set = map.keySet();
        Iterator<String> it = set.iterator();
        while (it.hasNext()){
            String temp = it.next();
            int tempN = map.get(temp);
            if (tempN == n){
                arrList.add(temp);
            }
        }
        return arrList;
    }


    public static boolean searchMatrix (int[][] matrix, int target) {
        // write code here
        if (matrix.length==0){
            return false;
        }
        int a =0;
        int b=matrix[0].length-1;
        while (a<matrix.length && b>-1){
            if (target == matrix[a][b]){
                return true;
            }
            if (target<matrix[a][b]){
                b--;
            }else if (target>matrix[a][b]){
                a++;
            }
        }
        return false;
    }

    public static ArrayList<ArrayList<Integer>> ReverseSentence(int sum) {
       ArrayList<ArrayList<Integer>> ar  = new ArrayList<>();
       for (int a=1;a<=sum/2;a++){
           ArrayList<Integer> arr = new ArrayList<>();
           int b=a;
           int tSum = sum;
           while (b<tSum){
               arr.add(b);
               tSum -=b;
               b++;
           }
           System.out.println(b+"  "+tSum);
           if (b==tSum){
               arr.add(b);
               ar.add(arr);
           }
       }
       return ar;
    }

    public static int getMinLen(int[] arr){

        if (arr.length<=1){
            return 1;
        }
        int max = 0;
        int minLen = Integer.MAX_VALUE;
        for (int a=1;a<arr.length;a++){
            for (int b=0;b+a<=arr.length;b++){
                int index = b;
                int res = 0;
                while (index<b+a){
                    res = res | arr[index];
                    index++;
                }
                if (res>max){
                    minLen = a;
                    max = res;
                   /* System.out.println(minLen+"   "+max);*/
                }
            }
        }
        return minLen;
    }





    public static int getKind(int a,int b){
        int n = Math.min(getMinZ(a),getMinZ(b));
        return 0;
    }

    public static int getMinZ(int a){
        for (int i=2;i<=a;i++){
            if (a%i==0){
                return i;
            }
        }
        return 1;
    }

    public static int getRes(String str){
        if (str==null || str.length()==1){
            return 0;
        }
        int mid = str.length()/2 ;
        int res =0;
        for (int a=0;a<mid;a++){
            if (str.charAt(a) != str.charAt(str.length()-a-1)){
                res++;
            }
        }
        return res;
    }


    //求小于N的所有质数
    public static ArrayList<Integer> getAll(int n){
        ArrayList<Integer> arrInt = new ArrayList<>();
        if (n==1){
            return  arrInt;
        }
        HashSet<Integer> set = new HashSet<>();
        for (int a=2;a<n;a++){
            if (!isZ(a)){
                arrInt.add(a);
                System.out.println(a);
            }
        }
        return arrInt;
    }

    public static boolean isZ(int n){
        for (int a=2;a<n;a++){
            if (n%a==0){
                return true;
            }
        }
        return false;
    }


    //打印一个全排列的思路  当前位置的字符 和 剩下位置的全排列的组合
    public String PrintMinNumber(int [] numbers) {
        ArrayList<String> arr = new ArrayList<>();
        for (int a: numbers){
            arr.add(String.valueOf(a));
        }
        int max = Integer.MIN_VALUE;
        for (String str : getAllList(arr)){
            int temp = Integer.parseInt(str);
            if (max<temp){
                max= temp;
            }
        }
        return String.valueOf(max);
    }

    public static ArrayList<String> getAllList(ArrayList<String> arrInt){
        ArrayList<String> arrayList = new ArrayList<>();
        if (arrInt.size() == 0){
            return arrayList;
        }
        if (arrInt.size() == 1){
            arrayList.add(arrInt.get(0));
            return arrayList;
        }
        for (int a=0;a<arrInt.size();a++){
            String str = arrInt.get(a);
            for (String s : getAllList(deleteAtIndex(arrInt,a))){
                arrayList.add(str+s);
            }
        }
        return arrayList;
    }

    public static ArrayList<String> deleteAtIndex(ArrayList<String> arrInt,int index){
        ArrayList<String> res = new ArrayList<>();
        for (int a=0;a<arrInt.size();a++){
            if (a!=index){
                res.add(arrInt.get(a));
            }
        }
        return res;
    }

    public static String getStrLessIndex(ArrayList<String> arrInt,int index){
        StringBuilder stringBuilder = new StringBuilder();
        for (int a = 0;a<arrInt.size();a++){
            if (a!=index){
                stringBuilder.append(arrInt.get(a));
            }
        }
        return stringBuilder.toString();
    }

    public String LeftRotateString(String str,int n) {
        StringBuilder stringBuilder = new StringBuilder();
        for (int a=0;a<str.length();a++){
            stringBuilder.append(str.charAt(n+a>str.length()?n+a-str.length() : n+a ));
        }
        return stringBuilder.toString();
    }

    //设计一个大根堆和一个小根堆 永远保证大根堆的最大值小于等于小根堆的最小值,在每次插入后进行一个平衡性调整
    PriorityQueue<Integer> min= new PriorityQueue<Integer>();
    PriorityQueue<Integer> max= new PriorityQueue<Integer>(16,new Mycom());
    public void Insert(Integer num) throws IOException {
        if (min.size()==0){
            min.add(num);
        }else if (max.size()==0){
            max.add(num);
        }else if (num <=min.peek()){
            max.add(num);
        }else {
        min.add(num);
        }
        balance();
    }
    public void balance(){
        while (min.size() - max.size() >1){
            max.add(min.poll());
        }
        while (max.size() - min.size() >1){
            min.add(max.poll());
        }
    }
    public Double GetMedian() {
        if (min.size()==max.size()){
            Double res = Double.valueOf(min.peek()+max.peek());
            return res/2;
        }
        return  min.size() >max.size() ?Double.valueOf(String.valueOf(min.peek()))
                :Double.valueOf(String.valueOf(max.peek()));
    }

    public static class Mycom implements Comparator<Integer>{
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2-o1;
        }
    }
}
